Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Знаходження максимального потоку в транспортній мережі.

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут прикладної математики та фундаментальних наук
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики

Інформація про роботу

Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Дискретна математика
Група:
ПМ-22

Частина тексту файла

Міністерство освіти та науки України Національний університет “Львівська політехніка” Інститут прикладної математики і фундаментальних наук Кафедра прикладної математики Лабораторна робота № 3 Знаходження максимального потоку в транспортній мережі Виконав: студент групи ПМ-22 Львів 2007 Умова задачі: 5.6. Знайти потік найбільшої величини для транспортної сітки: 01 12 23 15 05 06 76 57 68 78 37 34 56 48 49 89 4z 9z  7 10 15 4 10 11 17 18 21 23 19 14 15 17 10 19 19 25   Текст програми: #include <conio.h> #include <stdio.h> #include <iostream.h> //----------------------CONSTANTS AND VARIABLES------------ const kilver=11; //kilkist vershyn int x0=0; //pochatkova vershyna int z=10; //kinceva vershyna int c[kilver][kilver]={ //matrycya propusknyh spromognostey V-25 {0, 7, 0, 0, 0,10,11, 0, 0, 0, 0}, {0, 0,10, 0, 0, 4, 0, 0, 0, 0, 0}, {0, 0, 0,15, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0,14, 0, 0,19, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0,17,10,19}, {0, 0, 0, 0, 0, 0,15,18, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0,21, 0, 0}, {0, 0, 0, 0, 0, 0,17, 0,23, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0,19, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0,25}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} }; struct tochka { int nomer; int vidmichena; int znak; }; int pomicheni[kilver]; //masyp pomichenyh vershyn int f[kilver][kilver]; //matrycya potokiv po rebrah int potic; //max potik cherez meregu tochka path[kilver]; //masyv v jakomu vidobragaetsja shljah int pathlen; //dovgyna vybranogo shlyahu //----------------------FUNCTION PROTOTYPES---------------- void initialization(void); void pershyj_etap(void); void drugyj_etap(void); void vyvid(void); //void findpath(void); int min(tochka *path, int pathlen); //----------------------MAIN------------------------------- void main(void) {clrscr(); initialization(); pershyj_etap(); drugyj_etap(); vyvid(); getch();} //----------------------FUNCTION BODIES-------------------- void initialization(void) {potic=0; pathlen=0; for(int i=0; i<kilver; i++) { for(int j; j<kilver; j++) {f[i][j]=0;}; path[i].nomer=-1; pomicheni[i]=-1; } path[0].nomer=0;} //---------------------- void pershyj_etap(void) {int i; for (i=0;i<kilver;i++){path[i].znak=0;path[i].vidmichena=0;}; int pr=1; //praporec, vidpovidae za isnuvannya shljahu int minchyslo; for(;pr==1;) { for(int u=0;u<kilver;u++){path[u].nomer=-1;}; path[0].nomer=0; pathlen=0; i=0; for(;path[pathlen].nomer!=z;)//znahogennya shlyahu { for(int j=0;j<kilver;j++) //vybyraem nastupnu (sumignu) { pr=0; //shlyah ne isnue if(c[path[pathlen].nomer][j]-f[path[pathlen].nomer][j]>0) {//perevirka chy sumigne i chy propuskae she shos path[pathlen+1].nomer=j;/*path[j].vidmichena=1;break;*/ pathlen++; pr=1; //shlyah isnue i=path[pathlen].nomer; break; } } if(pr==0){break;}; }//for i if(pr==1) { minchyslo = min(path,pathlen); potic+=minchyslo; for(int i=0;i<pathlen;i++) { f[path[i].nomer][path[i+1].nomer]+=minchyslo; } pathlen=0; } }//for pr==1 } //---------------------- int min(tochka *path, int pathlen) {int ret=c[0][path[1].nomer]-f[0][path[1].nomer]; for(int i=1;i<pathlen+1;i++) { if((path[i+1].znak==1)+(path[i+1].vidmichena==0)==1) { if(c[path[i].nomer][path[i+1].nomer]-f[path[i].nomer][path[i+1].nomer]<ret) {ret=c[path[i].nomer][path[i+1].nomer]-f[path[i].nomer][path[i+1].nomer];}; } if(path[i+1].znak==-1) { if(f[path[i].nomer][path[i+1].nomer]<ret) {ret=f[path[i+1].nomer][path[i].nomer];}; } } return ret;} //---------------------- void drugyj_etap(void) {int i; for (i=0;i<kilver;i++){path[i].znak=0;path[i].vidmichena=-1;}; int pr=1; //praporec, vidpovidae za isnuvannya shljahu int minchyslo; int br; for(;pr==1;) { for(int u=0;u<kilver;u++) {path[u].nomer=-1;path[u].vidmichena=-1;path[u].znak=0;pomicheni[u]=-1;}; path[0].nomer=0; path[0].vidmichena=0; pomicheni[0]=1; pathlen=0; i=0; f...
Антиботан аватар за замовчуванням

01.01.1970 03:01

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини